from tools_algorithm import *


class Solution:
    def minDamage(self, power: int, damage: List[int], health: List[int]) -> int:
        mod = 1000000007
        t = [(v + power - 1) // power for v in health]
        a = []
        for i, (d, p) in enumerate(zip(damage, t)):
            a.append(((d / p), i))
        a.sort(reverse=True)
        s = sum(damage)
        ans = 0
        for v, i in a:
            ans += s * t[i]
            s -= damage[i]
        return ans

    # pow(p, mod - 2, mod)


s = Solution()
print(s.minDamage(power=1, damage=[1, 1, 1, 1], health=[1, 2, 3, 4]))
# print(s.minDamage(power=4, damage=[1, 2, 3, 4], health=[4, 5, 6, 8]))


class Solution:
    def minDamage(self, power: int, damage: List[int], health: List[int]) -> int:
        t = [(v + power - 1) // power for v in health]
        a = list(range(len(damage)))

        def f(i, j):
            return damage[j] * t[i] - damage[i] * t[j]

        a.sort(key=cmp_to_key(f))
        s = sum(damage)
        ans = 0
        for i in a:
            ans += s * t[i]
            s -= damage[i]
        return ans


s = Solution()
print(s.minDamage(power=1, damage=[1, 1, 1, 1], health=[1, 2, 3, 4]))
print(s.minDamage(power=4, damage=[1, 2, 3, 4], health=[4, 5, 6, 8]))
